Bài toán xếp ba lô có thể được giải trong thời gian giả-đa thức bằng quy hoạch động. Dưới đây là lời giải quy hoạch động cho bài toán xếp ba lô không bị chặn.

Gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Khi đó, với mỗi i ≤ C, đặt A(i) là giá trị lớn nhất có thể đạt được với tổng chi phí không vượt quá i. Rõ ràng, A(C) là đáp số của bài toán.

Định nghĩa A(i) một cách đệ quy như sau:

• A(0) = 0
• A(i) = max { vj + A(i − cj),A(i) | cj ≤ i }

Ở đây, giá trị lớn nhất của tập rỗng được lấy bằng 0. Tính dần các kết quả từ A(0) tới A(C), ta sẽ được lời giải. Do việc tính mỗi A(i) đòi hỏi xem xét n đồ vật (tất cả các giá trị này đã được tính từ trước), và có C giá trị của các A(i) cần tính, nên thời gian chạy của lời giải quy hoạch động là O(nC).

Điều này không mâu thuẫn với thực tế rằng bài toán xếp ba lô là NP-đầy đủ, do C, không như n, không thuộc mức đa thức theo độ dài của đầu vào cho bài toán. Độ dài đầu vào bài toán tỉ lệ thuận với số bit trong C, chứ không tỉ lệ với chính C.

Một giải pháp quy hoạch động tương tự cho bài toán xếp ba lô 0-1 cũng chạy trong thời gian giả-đa thức. Cũng như trên, gọi các chi phí là c1,..., cn và các giá trị tương ứng là v1,..., vn. Ta cần cực đại hóa tổng giá trị với điều kiện tổng chi phí không vượt quá C. Định nghĩa một hàm đệ quy A(i, j) là giá trị lớn nhất có thể đạt được với chi phí không vượt quá j và sử dụng các đồ vật trong khoảng từ x1 tới xi.

A(i,j) được định nghĩa đệ quy như sau:

• f[i][j]:= giá trị lớn nhất có thể lấy được;
• v[i]:= là giá trị của đồ vật thứ i;
• w[i]:=trọng lượng của đồ vật thứ i
• NOTES: Đây là bài toán không giới hạn đồ vật
• f[i][j]=max(f[i-1][j],v[i]+f[i][j-w[i]]) // khi đã lấy vật thứ i thì có thể lấy thêm nữa nên ta có f[i][j-w[i]]:= đã trừ đi trọng lượng của đồ vật thứ i và vẫn có thể lấy thêm được nữa // i là đồ vật không giới hạn
• A(0, j) = 0
• A(i, 0) = 0
• A(i, j) = A(i - 1, j) if ci > j
• A(i, j) = max(A(i - 1, j), vi + A(i - 1, j - ci)) if ci ≤ j

Để có lời giải, ta tính A(n, C). Để làm điều này, ta có thể dùng 1 bảng để lưu các tính toán trước đó. Cách giải này do đó sẽ chạy trong thời gian O(nC) và không gian O(nC), tuy ta có thể giảm độ phức tạp không gian xuống O(C) bằng một số sửa đổi nhỏ.